package com.leetcode.partition6;

import com.leetcode.common.TreeNode;

import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/8/22 9:42
 */
public class LC538把二叉搜索树转换为累加树 {

    public static TreeNode convertBST(TreeNode root) {
        reverseInorder(root);
        return root;
    }

    private static TreeNode pre = null;

    //反中序遍历，右中左
    private static void reverseInorder(TreeNode root) {
        if (root == null) return;
        reverseInorder(root.right);
        if (pre != null) root.val += pre.val;
        pre = root;
        reverseInorder(root.left);
    }

    private static void iteration(TreeNode root) {
        //栈反中序遍历
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root, pre = null;
        while (cur != null || !s.isEmpty()) {
            if (cur != null) {
                s.push(cur);
                cur = cur.right;
            } else {
                cur = s.pop();
                if (pre != null) cur.val += pre.val;
                pre = cur;
                cur = cur.left;
            }
        }
    }
}
